package com.c2b.algorithm.leetcode.base;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Objects;

/**
 * <a href='https://leetcode.cn/problems/closest-nodes-queries-in-a-binary-search-tree/'>二叉搜索树最近节点查询(Closest Nodes Queries in a Binary Search Tree)</a>
 * <p>给你一个 二叉搜索树 的根节点 root ，和一个由正整数组成、长度为 n 的数组 queries 。</p>
 * <p>
 * 请你找出一个长度为 n 的 二维 答案数组 answer ，其中 answer[i] = [mini, maxi] ：
 *     <ul>
 *         <li>mini 是树中小于等于 queries[i] 的 最大值 。如果不存在这样的值，则使用 -1 代替。</li>
 *         <li>maxi 是树中大于等于 queries[i] 的 最小值 。如果不存在这样的值，则使用 -1 代替。</li>
 *     </ul>
 * </p>
 * <p>返回数组 answer 。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1 ：
 *      输入：root = [6,2,13,1,4,9,15,null,null,null,null,null,null,14], queries = [2,5,16]
 *      输出：[[2,2],[4,6],[15,-1]]
 *      解释：按下面的描述找出并返回查询的答案：
 *          - 树中小于等于 2 的最大值是 2 ，且大于等于 2 的最小值也是 2 。所以第一个查询的答案是 [2,2] 。
 *          - 树中小于等于 5 的最大值是 4 ，且大于等于 5 的最小值是 6 。所以第二个查询的答案是 [4,6] 。
 *          - 树中小于等于 16 的最大值是 15 ，且大于等于 16 的最小值不存在。所以第三个查询的答案是 [15,-1] 。
 *
 * 示例 2 ：
 *      输入：root = [4,null,9], queries = [3]
 *      输出：[[-1,4]]
 *      解释：树中不存在小于等于 3 的最大值，且大于等于 3 的最小值是 4 。所以查询的答案是 [-1,4] 。
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>树中节点的数目在范围 [2, 10^5] 内</li>
 *         <li>1 <= Node.val <= 10^6</li>
 *         <li>n == queries.length</li>
 *         <li>1 <= n <= 10^5</li>
 *         <li>1 <= queries[i] <= 10^6</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/3/1 16:05
 */
public class LC2476ClosestNodesQueriesInBinarySearchTree_M {
    static class Solution {
        public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {
            List<Integer> arr = new ArrayList<>();
            // 中序遍历
            inorder(root, arr);
            List<List<Integer>> resList = new ArrayList<>();
            for (Integer query : queries) {
                int maxVal = -1;
                int minVal = -1;

                int idx = binarySearch(arr, query);
                if (idx != arr.size()) {
                    maxVal = arr.get(idx);
                    if (Objects.equals(arr.get(idx), query)) {
                        minVal = query;
                        resList.add(Arrays.asList(minVal, maxVal));
                        continue;
                    }
                }
                if (idx > 0) {
                    minVal = arr.get(idx - 1);
                }
                resList.add(Arrays.asList(minVal, maxVal));
            }
            return resList;
        }

        private void inorder(TreeNode root, List<Integer> inorderList) {
            if (root == null) {
                return;
            }
            inorder(root.left, inorderList);
            inorderList.add(root.val);
            inorder(root.right, inorderList);
        }

        private int binarySearch(List<Integer> arr, int target) {
            int low = 0;
            int high = arr.size();
            while (low < high) {
                int mid = low + ((high - low) >> 1);
                if (arr.get(mid) >= target) {
                    high = mid;
                } else {
                    low = mid + 1;
                }
            }
            return low;
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(6);
        root.left = new TreeNode(2);
        root.right = new TreeNode(13);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(9);
        root.right.right = new TreeNode(15);
        root.right.right.left = new TreeNode(14);
        Solution solution = new Solution();
        Printer.printListListInteger(solution.closestNodes(root, Arrays.asList(2, 5, 16)));
    }
}
